Batch 2 - Class 51 - Graphs III

Preclass Exercise:

(Dudeney - 375) FIVE JEALOUS HUSBANDS. During certain local floods five married couples found themselves surrounded by water, and had to escape from their unpleasant position in a boat that would only hold three persons at a time. Every husband was so jealous that he would not allow his wife to be in the boat or on either bank with another man (or with other men) unless he was himself present. Show the quickest way of getting these five men and their wives across into safety. Call the men A, B, C, D, E, and their respective wives a, b, c, d, e. To go over and return counts as two crossings. No tricks such as ropes, swimming, currents, etc., are permitted.
Answer:

Attendance: Tishyaa, Smiti, Diya, Muskaan, Rhea, Avy, Shubham, Anisha, Liza, Hriday, Aastha, Kushaan, Abhiram

Class Notes:

Review key concepts of Graphs

Eulerian Graphs

These are graphs where you can traverse the entire graph without lifting the pencil, and tracing every edge exactly once

MC Chap 5 - Problem 20 - Map of city of Konigsburg is given below. Can one stroll around the town, crossing each bridge exactly once?

Examples: Test if the following are Eulerian graphs or not?

Can you figure out common properties of Eulerian graphs?
Have to be connectedCount the number of vertices with odd edges (0 or 2) - Can it be 1?Duh! A graph can not have odd number of vertices with odd edges!Intuitively why does this make sense?
Look at City of Konigsburg and now look for an answer
4 vertices each with odd number of edges, so its not Eulerian!
Have you played Ticket to Ride? Can you go around this map in an Eulerian walk? (With and without double routes)
Can you find the longest path on ticket to ride if there was no limitation on number of tickets? (Ignore double routes because same player can not take them)

MC Chap 5 - Problem 22 - A piece of wire is 120 cm long. Can one use it to form edges of a cube, each of whose edge is 10 can, without cutting the wire?
No - this is same as an eulerian walk, but there are eight vertices each with three edges outWhat is the smallest number of cuts that one must make to be able to make the cube3 (two vertices can have 3 degree, so we are left with 6 vertices - three cuts in the wire can give us those three segments)

Applications of Graphs

Homework:

Dudeney - 381: Can you construct a card frame, one as shown below, so that each side adds up to the same number

References:

Mathematical Circles (Russian Experience), by Dmitri Fomin, Sergey Genkin, Ilia Itenberg